原贴地址：[http://blog.leanote.com/post/dawnmagnet/363](http://blog.leanote.c
om/post/dawnmagnet/363)
## 题目
给你一个 m x n 的矩阵 matrix 和一个整数 k 
，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。
题目数据保证总会存在一个数值和不超过 k 的矩形区域。
 
示例 1：
![](https://assets.leetcode.com/uploads/2021/03/18/sum-grid.jpg)
输入：matrix = [[1,0,1],[0,-2,3]], k = 2
输出：2
解释：蓝色边框圈出来的矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 
k 的最大数字（k = 2）。
示例 2：
输入：matrix = [[2,2,-1]], k = 3
输出：3
 
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-100 <= matrix[i][j] <= 100
-105 <= k <= 105
 
进阶：如果行数远大于列数，该如何设计解决方案？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
## 思路分析
我们首先观察一下该题，意思就是说计算一个矩形内部元素的和，如果我们对每个点进
行分别计算，复杂度就会达到O(n^3*m^3)，非常复杂，那么有没有什么简便的计算方法
呢？
大家会发现，很多地方我们都会重复计算，比如样例输入1中:
 - 左边矩形框（未画出）区域内的和是1+0+0+(-2)
 - 1周围r区域内的和是0+(-2)+1+3
可以观察得出，我们重复计算0+(-2)很多遍，那么如何减少重复计算呢？我想出来了一
个办法。